package com.homework;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-13
 * Time: 19:55
 */
//https://leetcode.cn/problems/smallest-k-lcci/submissions/395105577/
//快排思想？？？？
//class Solution {
//    public int[] smallestK(int[] arr, int k) {
//        int[] res = new int[k];
//        if (k == 0) {
//            return res;
//        }
//        //java默认为小根堆，我们需要自己改为大根堆
//        PriorityQueue<Integer> priQueue = new PriorityQueue<>(new Comparator<Integer>(){
//            public int compare(Integer num1, Integer num2) {
//                return num2 - num1;
//            }
//        });
//        //将前k个放入堆
//        for (int i = 0; i < k; i++) {
//            priQueue.offer(arr[i]);
//        }
//        for (int i = k; i < arr.length; i++) {
//            //堆顶为最大值，若后面有更小的，弹出堆顶，放入更小值，然后重新调整为大根堆
//            if (priQueue.peek() > arr[i]) {
//                priQueue.poll();
//                priQueue.offer(arr[i]);
//            }
//        }
//        //将堆拷贝到数组
//        for (int i = 0; i < k; i++) {
//            res[i] = priQueue.poll();
//        }
//        return res;
//    }
//
//}
